package com.zpself.module.算法练习.二叉树;


import java.util.*;

/**
 * 二叉树的先序遍历  中、左、右
 * 二叉树的中序遍历  左、中、右
 * 二叉树的后序遍历  左、右、中
 * @author By ZengPeng
 * @Description
 * @date in  2020/9/29 15:34
 * @Modified By
 */
public class 二叉树3种遍历 {
    public static void main(String[] args) {
        TreeNode root = TreeNode.initRoot();
        二叉树3种遍历 liKou_145 = new 二叉树3种遍历();
//        -------------------------先续遍历：-------------------------
//        List<Integer> preorderTraverseResult = liKou_145.preorderTraverse(root);
//        System.out.println(preorderTraverseResult);


//        -------------------------中续遍历：-------------------------
        List<Integer> middleTraverseResult = liKou_145.middleTraverse(root);
        System.out.println(middleTraverseResult);


//      -------------------------后续遍历：-------------------------
        //循环+队列
//        List<Integer> postorderTraverseResult = liKou_145.postorderTraversal_me(root);
//        System.out.println(postorderTraverseResult);
        //循环+队列
//        List<Integer> postorderTraverseResult = liKou_145.postorderTraversal_good(root);
//        System.out.println(postorderTraverseResult);
        //递归
//        List<Integer> integers = liKou_145.postorderTraversal(root);
    }

    /**
     *  中续遍历:循环+队列
     * @param  root 树
     * @author  ZengPeng
     * @date  2020/10/9
     **/
    public List<Integer> middleTraverse(TreeNode root) {
        TreeNode p = root;//当前节点
        List<Integer>ans = new ArrayList<>();//结果顺序集合
        Deque<TreeNode> s = new ArrayDeque<>();//双端队列，感觉直接队列也行阿
        s.push(p);
        while(!s.isEmpty()) {
            p = s.poll();
            if(p.right==null && p.left==null)
                ans.add(p.val);
            else {
                if(p.right!=null)//不为null,压栈
                    s.push(p.right);

                s.push(new TreeNode(p.val));//当前节点

                if(p.left!=null)//不为null,压栈
                    s.push(p.left);
            }

        }
        return  ans;
    }

    /**
     *  先续遍历:循环+队列
     * @param  root 树
     * @author  ZengPeng
     * @date  2020/10/9
     **/
    public List<Integer> preorderTraverse(TreeNode root) {
        TreeNode p = root;//当前节点
        List<Integer>ans = new ArrayList<>();//结果顺序集合
        Deque<TreeNode> s = new ArrayDeque<>();//双端队列，感觉直接队列也行阿
        s.push(p);
        while(!s.isEmpty()) {
            p = s.poll();
            if(p.right!=null){//不为null,压栈
                s.push(p.right);
            }
            if(p.left!=null){//不为null,压栈
                s.push(p.left);
            }
            ans.add(p.val);
        }
        return  ans;
    }
    /**
     *  后续遍历:循环+队列
     * @param  root 树
     * @author  ZengPeng
     * @date  2020/10/9
     **/
    public List<Integer> postorderTraversal_good(TreeNode root) {
        TreeNode p = root;//当前节点
        TreeNode r = null;//上一个存储的值
        List<Integer>ans = new ArrayList<>();//结果顺序集合
        Deque<TreeNode> s = new ArrayDeque<>();//双端队列，感觉直接队列也行阿
        while(!s.isEmpty() || p != null) {
            if(p != null) {
                s.push(p);p = p.left;//先遍历最左端的
            } else {
                p = s.peek();//查栈
                if(p.right == null || p.right == r) {//判断右边 是否为空？ 或者右边的刚才已经存储（r）了
                    ans.add(p.val);//存储当前节点
                    r = p;//记录R
                    s.pop();//弹栈
                    p = null;
                } else
                    p = p.right;//右边树还没遍历呢....
            }
        }
        return  ans;
    }

    /**
    *  后续遍历递归
    * @param  root 树
    * @author  ZengPeng
    * @date  2020/10/9
    **/
    public List<Integer> postorderTraversal(TreeNode root) {
        //创建返回集合
        List<Integer> result = new ArrayList<>();
        if(root!=null){

            if(root.left!=null){
                result.addAll(postorderTraversal(root.left));
            }
            if(root.right!=null){
                result.addAll(postorderTraversal(root.right));
            }
            result.add(root.val);
        }
        //遍历左边、右边、自己
        return  result;
    }
    /**
     *  后续遍历递归
     * @param  root 树
     * @author  ZengPeng
     * @date  2020/10/9
     **/
    public List<Integer> postorderTraversal_me(TreeNode root) {
        TreeNode p = root;//当前节点
        List<Integer>ans = new ArrayList<>();//结果顺序集合
        Deque<TreeNode> s = new ArrayDeque<>();//双端队列，感觉直接队列也行阿
        s.push(p);
        while(!s.isEmpty()) {
            p = s.poll();
            if(p.right==null && p.left==null){
                ans.add(p.val);
                continue;
            }
            s.push(p);
            if(p.right!=null){
                s.push(p.right);
                p.right=null;
            }
            if(p.left!=null){
                s.push(p.left);
                p.left=null;
            }
        }
        return  ans;
    }
}
